{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 背包问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 问题背景"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们在出行的时候，一定遇到过这样的问题，想带的东西很多，但是无奈背包容量有限。那么在这种情况下我们需要对带的物品进行一些取舍，这就是背包问题的由来。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 01背包问题\n",
    "假设我们有n个物品，第i个物品大小为a[i]，有一个容量大小为m的背包，问最多能装走多重的物品？\n",
    "\n",
    "举一个实际的例子：\n",
    "背包大小容量为10，我们想尽量装满背包。\n",
    "\n",
    "我们有以下物品：\n",
    "\n",
    "| 物品 | 体积| \n",
    "| :---: | :---: |\n",
    "| 可乐 | 4 |\n",
    "| 薯片 | 6 |\n",
    "| 自热火锅 | 9 |\n",
    "\n",
    "方案1：优先放体积最大的，那么我们只能拿到一个自热火锅，使用的总体积为9。(这也说明了背包问题不能通过贪心解决)\n",
    "\n",
    "方案2：同时拿可乐和薯片，我们可以把背包装满。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 动态规划解法\n",
    "#### 假设我们只有一个物品可乐，我们知道体积为4。\n",
    "我们设一个数组`dp[i][j]`表示前`i`个物品，放满容量为`j`的空间是否可行。那么首先`dp[0][0] = 0`，因为我们用`0`个物品总是可以放满0的空间，而对于dp[1]，我们有:\n",
    "\n",
    "| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |\n",
    "| - | - | - | - | - | - | - | - | - | - | - | - |\n",
    "| dp[1] | True | False | False | False | True | False | False | False | False | False | False|\n",
    "\n",
    "`dp[1][0]`为`True`，是因为我们可以不取这个物品，这样我们的体积依旧为`0`。`dp[1][4]`为`True`，因为我们可以取这个物品，这样我们的背包里体积就用了`4`了。\n",
    "\n",
    "#### 我们再添加一个薯片进去，薯片体积为6\n",
    "我们现在是有两个物品了，对应的，`dp[2]`为：\n",
    "\n",
    "| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |\n",
    "| - | - | - | - | - | - | - | - | - | - | - | - |\n",
    "| dp[1] | True | False | False | False | True | False | False | False | False | False | False|\n",
    "| dp[2] | True | False | False | False | True | False | <font color=\"red\">True</font> | False | False | False | <font color=\"red\">True</font>|\n",
    "\n",
    "可以看到，相较于`dp[1]`，在`dp[2]`中，`dp[2][6]`和`dp[2][10]`也为`True`。也即分别对应取或者不取第二个物品的情况。\n",
    "\n",
    "所以我们有我们的推断过程：\n",
    "如果`dp[i][j]=True`，即前i个物品通过取舍有办法放满容量为j的空间，那么对于第`i+1`个物品,我们可以知道：\n",
    "\n",
    "1. $$dp[i+1][j+a[i+1]] = True$$ 我们在前面的基础上，再拿一个体积为`a[i+1]`物品，即可使前`i+1`个物品占满容量为`j+a[i+1]`的空间。\n",
    "\n",
    "\n",
    "2. $$dp[i+1][j] = True$$ 前`i`个物品可以有办法凑到`j`的空间，那么前`i+1`个物品肯定有办法，即直接采用前面的策略，我们不拿第`i+1`个物品就是了。\n",
    "\n",
    "#### 实现我们的动态规划解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ True, False, False, False, False, False, False, False, False,\n",
       "        False, False],\n",
       "       [False, False, False, False, False, False, False, False, False,\n",
       "        False, False],\n",
       "       [False, False, False, False, False, False, False, False, False,\n",
       "        False, False],\n",
       "       [False, False, False, False, False, False, False, False, False,\n",
       "        False, False]])"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#输入物品的重量,物品个数和背包大小\n",
    "a = [4,6,9]\n",
    "n = len(a)\n",
    "m = 10\n",
    "\n",
    "#定义动态规划数组\n",
    "import numpy as np\n",
    "dp = np.zeros((n+1,m+1),dtype=np.bool)\n",
    "#初始化\n",
    "dp[0][0] = True\n",
    "\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ True, False, False, False, False, False, False, False, False,\n",
       "        False, False],\n",
       "       [ True, False, False, False,  True, False, False, False, False,\n",
       "        False, False],\n",
       "       [ True, False, False, False,  True, False,  True, False, False,\n",
       "        False,  True],\n",
       "       [ True, False, False, False,  True, False,  True, False, False,\n",
       "         True,  True]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in range(1,n+1): #枚举物品\n",
    "    for j in range(m+1):\n",
    "        dp[i][j] = False\n",
    "        #如果要让dp[i][j]为true，则dp[i-1][j]和dp[i-1][j-a[i-1]]必然有一个为true\n",
    "        dp[i][j] |= dp[i-1][j] #情况1\n",
    "        if j >= a[i-1]:\n",
    "            dp[i][j] |= dp[i-1][j-a[i-1]] #情况2\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#最终我们需要知道最多能装多重的物品\n",
    "ans = 0\n",
    "for j in range(m,-1,-1):\n",
    "    if dp[n][j]: #如果前n个物品正好能装满容量为j的空间\n",
    "        ans = j\n",
    "        break\n",
    "ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 带权重的01背包"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们刚才只考虑了背包尽量装满，但是有时候我们的物品可能有不同的价值。\n",
    "\n",
    "我们将物品都赋予一定的价值：\n",
    "\n",
    "| 物品 | 体积| 价值 |\n",
    "| :---: | :---: | :---: |\n",
    "| 可乐 | 4 | 1 |\n",
    "| 薯片 | 6 | 2 |\n",
    "| 自热火锅 | 9 | 5 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "还是来看两个方案：\n",
    "\n",
    "方案1：只拿一个自热火锅，虽然背包没装满，但是总价值是5\n",
    "\n",
    "方案2：同时拿可乐和薯片，我们可以把背包装满，但是总价值只有3\n",
    "\n",
    "### 我们需要修改一下DP的状态含义\n",
    "我们设一个数组`dp[i][j]`表示前`i`个物品，放满容量为`j`的空间~~是否可行~~**的最大价值**。那么首先`dp[0][0] = 0`，因为我们用`0`个物品总是可以放满0的空间，由于没有拿物品，所以价值为0。\n",
    "\n",
    "我们也需要更新我们的状态转移方程：\n",
    "对于`dp[i][j]`状态，即前i个物品通过取舍有办法放满容量为j的空间，那么这种状态有可能从两个状态转移而来\n",
    "\n",
    "1. 我们拿了第`i`个物品，那么拿了第`i`个物品后体积为`j`，没拿第`i`个物品的时候体积肯定为`j-a[i]`，所以相邻状态为`dp[i-1][j-a[i]]`\n",
    "\n",
    "2. 我们没拿第`i`个物品，那么在前面`i-1`个物品我们需要有办法得到j的空间，所以相邻状态为`dp[i-1][j]`\n",
    "\n",
    "#### 实现我们的动态规划解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#输入物品的重量,物品个数，价值和背包大小\n",
    "a = [4,6,9]\n",
    "v = [1,2,5]\n",
    "n = len(a)\n",
    "m = 10\n",
    "\n",
    "#定义动态规划数组\n",
    "import numpy as np\n",
    "dp = np.zeros((n+1,m+1))\n",
    "\n",
    "#初始化\n",
    "dp.fill(-1) #赋值-1代表暂时不可行\n",
    "dp[0][0] = 0\n",
    "\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [ 0., -1., -1., -1.,  1., -1., -1., -1., -1., -1., -1.],\n",
       "       [ 0., -1., -1., -1.,  1., -1.,  2., -1., -1., -1.,  3.],\n",
       "       [ 0., -1., -1., -1.,  1., -1.,  2., -1., -1.,  5.,  3.]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in range(1,n+1): #枚举物品\n",
    "    for j in range(m+1):\n",
    "        if dp[i-1][j] != -1:\n",
    "            dp[i][j] = max(dp[i][j], dp[i-1][j]) #不取第i个物品\n",
    "        if j >= a[i-1] and dp[i-1][j-a[i-1]] != -1:\n",
    "            dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1]]+v[i-1]) #取第i个物品\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#最终我们需要知道最多能装多贵的物品\n",
    "ans = max(dp[n])\n",
    "ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. 路径记录\n",
    "我们刚才只回答了如何得到最优的结果，但是并未回答最优的装配方案是什么\n",
    "\n",
    "### DP的同时记录最优路径\n",
    "\n",
    "我们前面提到，对于`dp[i][j]`状态，即前i个物品通过取舍有办法放满容量为j的空间，那么这种状态有可能从`dp[i-1][j-a[i]]`和`dp[i-1][j]`两个状态转移而来。\n",
    "\n",
    "而实际上，如果从`dp[i-1][j-a[i]]`转移而来，则表示第i个物品会取，否则如果从`dp[i-1][j]`转移而来，则表示第i个物品不选。\n",
    "\n",
    "因此我们在动态规划的时候，可以用一个额外的path数组记录每个值的转移路径，最终照着路径反向找到方案。\n",
    "#### 实现我们的动态规划解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#输入物品的重量,物品个数，价值和背包大小\n",
    "a = [4,6,9]\n",
    "v = [1,2,5]\n",
    "n = len(a)\n",
    "m = 10\n",
    "\n",
    "#定义动态规划数组\n",
    "import numpy as np\n",
    "dp = np.zeros((n+1,m+1))\n",
    "\n",
    "#定义路径数组\n",
    "path = np.zeros((n+1,m+1))\n",
    "\n",
    "#初始化\n",
    "dp.fill(-1) #赋值-1代表暂时不可行\n",
    "dp[0][0] = 0\n",
    "\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [ 0., -1., -1., -1.,  1., -1., -1., -1., -1., -1., -1.],\n",
       "       [ 0., -1., -1., -1.,  1., -1.,  2., -1., -1., -1.,  3.],\n",
       "       [ 0., -1., -1., -1.,  1., -1.,  2., -1., -1.,  5.,  3.]])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in range(1,n+1): #枚举物品\n",
    "    for j in range(m+1):\n",
    "        if dp[i-1][j] != -1:\n",
    "            if dp[i][j] < dp[i-1][j]:\n",
    "                dp[i][j] = dp[i-1][j] # 不取第i个物品\n",
    "                path[i][j] = 1 #表示dp[i][j]由情况1转移而来\n",
    "        if j >= a[i-1] and dp[i-1][j-a[i-1]] != -1:\n",
    "            if dp[i][j] < dp[i-1][j-a[i-1]]+v[i-1]:\n",
    "                dp[i][j] = dp[i-1][j-a[i-1]]+v[i-1] #取第i个物品\n",
    "                path[i][j] = 2 #表示dp[i][j]由情况2转移而来\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],\n",
       "       [1., 0., 0., 0., 2., 0., 0., 0., 0., 0., 0.],\n",
       "       [1., 0., 0., 0., 1., 0., 2., 0., 0., 0., 2.],\n",
       "       [1., 0., 0., 0., 1., 0., 1., 0., 0., 2., 1.]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#我们path已经记录好了转移路径\n",
    "path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "use 2\n"
     ]
    }
   ],
   "source": [
    "#最终我们需要知道最多能装多贵的物品\n",
    "j = np.argmax(dp[n])\n",
    "\n",
    "#反向回溯找路径\n",
    "i = n # 最终最优状态为dp[i][j]\n",
    "while ( i != 0 ):\n",
    "    if path[i][j] == 1: # 第i个数不取\n",
    "        pass\n",
    "    else: # 第i个数取\n",
    "        print('use %d'%(i-1))\n",
    "        j -= a[i-1]\n",
    "    i -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. 空间优化\n",
    "我们前面的做法中，都使用到了`dp`这个二维数组，因此空间复杂度为`O（n\\*m）`。但是实际上`dp[i]`的结果只和`dp[i-1]`有关，我们要计算`dp[i]`的时候，`dp[i-1]`之前的结果已经再也不会被用到了。因此，我们可以采用滚动数组技术来优化空间。\n",
    "\n",
    "### 滚动数组\n",
    "我们减少我们的dp数组维度到`dp[2][m]`，现在来看看如何两个维度完成计算。\n",
    "\n",
    "1. 最开始的时候，`dp[0]`和`dp[1]`和之前的计算过程一致，接下来，我们主要讲解`dp[2]`如何计算。\n",
    "2. 按之前的方程，`dp[2][j] = min(dp[1][j], dp[1][j-a[1]]+w[1])`,但是我们现在数组没有第二维，那么我们可以把第0维重新利用起来，方程改为：`dp[0][j] = min(dp[1][j], dp[1][j-a[1]]+w[1])`，那么这里的`dp[0][j]`就是我们的`dp[2][j]`的值了。\n",
    "3. 如果我们继续计算`dp[3]`，这次我们会把`dp[3]`的值记录在数组的第一维，这样直观来看，数组的两个维度在不停地滚动，因此这个数组也叫做滚动数组。\n",
    "\n",
    "但是注意，因为我们现在只有两个维度的信息了，如果使用滚动数组优化了空间，我们就无法再记录方案了。\n",
    "\n",
    "#### 实现我们的动态规划解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1.]])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#输入物品的重量,物品个数，价值和背包大小\n",
    "a = [4,6,9]\n",
    "v = [1,2,5]\n",
    "n = len(a)\n",
    "m = 10\n",
    "\n",
    "#定义动态规划数组\n",
    "import numpy as np\n",
    "dp = np.zeros((2,m+1))#现在第一维只需要2了\n",
    "\n",
    "#初始化\n",
    "dp.fill(-1) #赋值-1代表暂时不可行\n",
    "dp[0][0] = 0\n",
    "\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., -1., -1., -1.,  1., -1.,  2., -1., -1., -1.,  3.],\n",
       "       [ 0., -1., -1., -1.,  1., -1.,  2., -1., -1.,  5.,  3.]])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in range(1,n+1): #枚举物品\n",
    "    k = i % 2 # k表示现在要把结果记录在哪一维\n",
    "    for j in range(m+1):\n",
    "        if dp[1-k][j] != -1: #因为现在只有两维了，我们把结果记录在第k维，那么用于计算的维度自然是1-k\n",
    "            dp[k][j] = max(dp[k][j], dp[1-k][j]) #不取第i个物品\n",
    "        if j >= a[i-1] and dp[1-k][j-a[i-1]] != -1:\n",
    "            dp[k][j] = max(dp[k][j], dp[1-k][j-a[i-1]]+v[i-1]) #取第i个物品\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#最终我们需要知道最多能装多贵的物品\n",
    "ans = max(dp[k])\n",
    "ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. 完全背包\n",
    "我们之前的题目里，每个物品都是只有一个的，那么如果每个物品都有无限个，该如何解决？\n",
    "\n",
    "假设我们现在有一个状态`dp[i][j]`,现在考虑第i+1个物品。\n",
    "1. 第`i+1`个物品不取，我们会得到`dp[i+1][j]`状态\n",
    "2. 第`i+1`个物品取一个，我们会得到`dp[i+1][j+a[i]]`状态\n",
    "3. 第`i+1`个物品取两个，我们会得到`dp[i+1][j+2*a[i]]`状态\n",
    "4. 。。。\n",
    "\n",
    "我们来思考一下`dp[i+1][j]`和`dp[i+1][j+a[i]]`，如果我们已经得到`dp[i+1][j]`的最优值了，那么再取一个`i+1`物品等价于在`dp[i+1][j]`的基础上再取一个物品。同理，`dp[i+1][j+2*a[i]]`也等价于在`dp[i+1][j+a[i]]`的基础上再取一个i+1物品。\n",
    "\n",
    "所以，在完全背包问题中，`dp[i][j]`不光会从`dp[i-1][j]`,`dp[i-1][j-a[i]]`来，**也会从`dp[i][j-a[i]]`**来。所以现在的方程为：\n",
    "$$dp[i][j] = min(dp[i-1][j],dp[i-1][j-a[i]]+w[i],dp[i][j-a[i]]+w[i])$$\n",
    "\n",
    "#### 实现我们的动态规划解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1.]])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#输入物品的重量,物品个数，价值和背包大小\n",
    "a = [4,6,9]\n",
    "v = [1,2,5]\n",
    "n = len(a)\n",
    "m = 8\n",
    "\n",
    "#定义动态规划数组\n",
    "import numpy as np\n",
    "dp = np.zeros((n+1,m+1))\n",
    "\n",
    "#初始化\n",
    "dp.fill(-1) #赋值-1代表暂时不可行\n",
    "dp[0][0] = 0\n",
    "\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [ 0., -1., -1., -1.,  1., -1., -1., -1.,  1.],\n",
       "       [ 0., -1., -1., -1.,  1., -1.,  2., -1.,  1.],\n",
       "       [ 0., -1., -1., -1.,  1., -1.,  2., -1.,  1.]])"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in range(1,n+1): #枚举物品\n",
    "    for j in range(m+1):\n",
    "        if dp[i-1][j] != -1:\n",
    "            dp[i][j] = max(dp[i][j], dp[i-1][j]) #不取第i个物品\n",
    "        if j >= a[i-1] and dp[i-1][j-a[i-1]] != -1:\n",
    "            dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1]]+v[i-1]) #取第i个物品\n",
    "        if j >= a[i-1]:#完全背包的情况，还可以从dp[i][j-a[i-1]]转移过来\n",
    "            dp[i][j] = max(dp[i][j],dp[i][j-a[i-1]])\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#最终我们需要知道最多能装多贵的物品\n",
    "ans = max(dp[n])\n",
    "ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7. 分组背包\n",
    "还有一种比较有意思的场景。例如我们带东西出门，有些东西我们有很多选择，例如我们要带一瓶水，我们可以带小瓶的农夫山泉，也可以带大瓶的脉动，但是我们不会带上所有的水，可能最后我们只会带一种。\n",
    "那么抽象一下，我们有n组物品，每组中的物品也有体积和价值，但是我们只能拿一个。问能带走的最大价值。\n",
    "\n",
    "其实本质上来说，分组背包和01背包并没有太大区别。可以这么来考虑，我们可以认为01背包是分组背包的一个特殊情况，每一组只有一个物品，那么对应于每一组的策略我们有`不取`和`取物品1`。但是分组背包，每一组的策略是`不取`，`取物品1`，`取物品2`。。。可以看到只是可选策略变多了，其他没有变化。\n",
    "\n",
    "那么，我们假设a[i][j]代表第i组的第j个物品的体积，w[i][j]代表第i组的第j个物品的价值，我们现在的转移方程变为：\n",
    "\n",
    "\n",
    "$$dp[i][j] = min(dp[i-1][j],\\min_{k=0}^{len(a[i])}[dp[i-1][j-a[i][k]]+w[i][k]])$$\n",
    "\n",
    "#### 实现我们的动态规划解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [-1., -1., -1., -1., -1., -1., -1., -1., -1.]])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#输入物品的重量,物品个数，价值和背包大小\n",
    "a = [[1,2],[3,2,1],[6,4,2]]\n",
    "v = [[3,1],[3,2,1],[3,4,2]]\n",
    "n = len(a)\n",
    "m = 8\n",
    "\n",
    "#定义动态规划数组\n",
    "import numpy as np\n",
    "dp = np.zeros((n+1,m+1))\n",
    "\n",
    "#初始化\n",
    "dp.fill(-1) #赋值-1代表暂时不可行\n",
    "dp[0][0] = 0\n",
    "\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., -1., -1., -1., -1., -1., -1., -1., -1.],\n",
       "       [ 0.,  3.,  1., -1., -1., -1., -1., -1., -1.],\n",
       "       [ 0.,  3.,  4.,  5.,  6.,  4., -1., -1., -1.],\n",
       "       [ 0.,  3.,  4.,  5.,  6.,  7.,  8.,  9., 10.]])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in range(1,n+1): #枚举组\n",
    "    for j in range(m+1):\n",
    "        if dp[i-1][j] != -1:\n",
    "            dp[i][j] = max(dp[i][j], dp[i-1][j]) #不取第i个物品\n",
    "        for k in range(len(a[i-1])):#枚举组内的物品\n",
    "            if j >= a[i-1][k] and dp[i-1][j-a[i-1][k]] != -1:\n",
    "                dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1][k]]+v[i-1][k]) #取组内第k个物品\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.0"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#最终我们需要知道最多能装多贵的物品\n",
    "ans = max(dp[n])\n",
    "ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8. 多重背包\n",
    "虽然一个背包我们已经有很好的办法优化了，但是最土豪的方式还是多带一个背包。多重背包问题是，当我们有两个背包的时候，该如何规划我们的方案呢？\n",
    "\n",
    "还是和之前一样，我们从我们的的策略出发来思考，那么对于一个物品，他有三种可能的方式：\n",
    "1. 丢弃\n",
    "2. 放进背包1\n",
    "3. 放进背包2\n",
    "\n",
    "我们之前的状态为dp[i][j]，表示前i个物品装满容量为j的背包的最大价值。那么我们可以把状态扩大一维，dp[i][j][k]代表前i个物品，第一个背包正好装了j，第二个背包正好装了k的最大价值。对应的，状态转移方程变为：\n",
    "\n",
    "$$dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a[i]][k]+w[i],dp[i-1][j][k-a[i]]+w[i])$$\n",
    "\n",
    "#### 实现我们的动态规划解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[[ 0., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.]],\n",
       "\n",
       "       [[-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.]],\n",
       "\n",
       "       [[-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.]],\n",
       "\n",
       "       [[-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.]]])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#输入物品的重量,物品个数，价值和背包大小\n",
    "a = [4,6,9]\n",
    "v = [1,2,5]\n",
    "n = len(a)\n",
    "m1 = 8\n",
    "m2 = 4\n",
    "#定义动态规划数组\n",
    "import numpy as np\n",
    "dp = np.zeros((n+1,m1+1,m2+1))\n",
    "\n",
    "#初始化\n",
    "dp.fill(-1) #赋值-1代表暂时不可行\n",
    "dp[0][0][0] = 0\n",
    "\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[[ 0., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.]],\n",
       "\n",
       "       [[ 0., -1., -1., -1.,  1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [ 1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.]],\n",
       "\n",
       "       [[ 0., -1., -1., -1.,  1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [ 1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [ 2., -1., -1., -1.,  3.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.]],\n",
       "\n",
       "       [[ 0., -1., -1., -1.,  1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [ 1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [ 2., -1., -1., -1.,  3.],\n",
       "        [-1., -1., -1., -1., -1.],\n",
       "        [-1., -1., -1., -1., -1.]]])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in range(1,n+1): #枚举物品\n",
    "    for j in range(m1+1):\n",
    "        for k in range(m2+1):\n",
    "            if dp[i-1][j][k] != -1:\n",
    "                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]) #不取第i个物品\n",
    "            if j >= a[i-1] and dp[i-1][j-a[i-1]][k] != -1:\n",
    "                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-a[i-1]][k]+v[i-1]) #取第i个物品,放入背包1\n",
    "            if k >= a[i-1] and dp[i-1][j][k-a[i-1]] != -1:\n",
    "                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-a[i-1]]+v[i-1]) #取第i个物品,放入背包2\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.0"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#最终我们需要知道最多能装多贵的物品\n",
    "ans = np.max(dp[n])\n",
    "ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.总结\n",
    "我们介绍了动态规划的一类基础问题——背包问题，并介绍了包括01背包，完全背包，多重背包等各种背包问题的变种。很多动态规划问题都有许多变种，其实大部分的思想都不会有太大改变，我们只需要重新思考当前情形下的转移方程就可以很好地解决了。\n",
    "背包问题也是经典和高频的面试题目，大家需要熟悉相关的实现过程。"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
